#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

//方法一：**
void reserve(char* s)
{
    char tmp;
    int r = strlen(p)-1;
    int l =0;
    while(l<r){
        tmp = p[l];
        p[l]=p[r];
        p[r]=tmp;
        l++;
        r--;
    }
}
char* addBinary(char* a, char* b)
{
    reserve(a);
    reserve(b);
    int len1 = strlen(a);
    int len2 = strlen(b);
    int n = fmax(len1, len2);//返回最大数
    int carry = 0;
    int len = 0;
    char* ans = (char*)malloc((n + 2) * sizeof(char));/* 长度可能是更长的字符串加1 */
    for (int i = 0; i < n; i++)
    {
        carry += i < len1 ? (a[i] == '1') : 0;
        carry += i < len2 ? (b[i] == '1') : 0;

        ans[len++] = carry % 2 + '0';
        carry /= 2;
    }
    if (carry)
    {
        ans[len++] = '1';
    }
    ans[len] = '\0';
    reserve(ans);
    return ans;
}


//void reserve(char* s) {
//    int len = strlen(s);
//    for (int i = 0; i < len / 2; i++) {
//        char t = s[i];
//        s[i] = s[len - i - 1], s[len - i - 1] = t;
//          //交换第i位和倒数第i位的数
//    }
//}

//char* addBinary(char* a, char* b) {
//    reserve(a);
//    reserve(b);
//
//    int len_a = strlen(a), len_b = strlen(b);
//    int n = fmax(len_a, len_b), carry = 0, len = 0;
//    char* ans = (char*)malloc(sizeof(char) * (n + 2));
//    for (int i = 0; i < n; ++i) {
//        carry += i < len_a ? (a[i] == '1') : 0;
//        carry += i < len_b ? (b[i] == '1') : 0;
//        ans[len++] = carry % 2 + '0';
//        carry /= 2;
//    }
//
//    if (carry) {
//        ans[len++] = '1';
//    }
//    ans[len] = '\0';
//    reserve(ans);
//
//    return ans;
//}

//解法二：
//char* addBinary(char* a, char* b) {
//    int lena = strlen(a);
//    int lenb = strlen(b);
//
//    int len = lena > lenb ? lena : lenb;
//    char* res = (char*)malloc(sizeof(char) * (len + 2));	//+2防进位
//    res[++len] = 0;
//
//    char carry = '0';
//    char pa, pb;
//    while (len > 1 || carry == '1') {
//        pa = lena > 0 ? a[--lena] : '0';
//        pb = lenb > 0 ? b[--lenb] : '0';						//处理长度不一的情况
//
//        res[--len] = pa ^ pb ^ carry; 						// 当前位
//        carry = (pa & carry) | (pb & carry) | (pa & pb); 	//进位
//    }
//
//    return res + len;										//返回 res 的第 len 到末尾的字符
//}

//方法三：*******
char * addBinary(char * a, char * b)
{
  
    int carry = 0;
    int lena = strlen(a);
    int lenb = strlen(b);
    int len  = fmax(lena, lenb);
    int i    = lena - 1;
    int j    = lenb - 1;
    char *res = (char*)malloc(sizeof(char) * (len + 2)); /* 长度可能是更长的字符串加1 */
    int k = len + 1;
    res[k--] = '\0'; /* 添加结束符 */
 
    /* 模拟加法处理 */
    while (i >= 0 || j >= 0 || carry > 0) {
        carry += (i >= 0) ? a[i--] - '0' : 0;
        carry += (j >= 0) ? b[j--] - '0' : 0;
        res[k--] = carry % 2 + '0';
        carry /= 2;
    }
    return res+k+1 ; //因为预留多一位用来最高位进位，若没有进位res[0]就没有值则不能直接返回res，而是返回第二个元素地址，修改为res+1,但有进位时又要返回首元素地址，则应该改为res+k+1
}

int main()
{
    char arr1[] = "11";
    char arr2[] = "1";
    addBinary(arr1, arr2);
    printf("%s", addBinary(arr1, arr2));
    return 0;
}